import java.util.*;
//310. 最小高度树
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> ans = new ArrayList<>();
        if (n == 1) { // 特例：只有一个节点
            ans.add(0);
            return ans;
        }

        // 1. 构建邻接表
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] degree = new int[n]; // 记录每个节点的度数
        for (int i = 0; i < n; i++) graph.put(i, new ArrayList<>());
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            graph.get(u).add(v);
            graph.get(v).add(u);
            degree[u]++;
            degree[v]++;
        }

        // 2. 找到所有叶子节点（度为 1）
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) queue.offer(i);
        }

        // 3. 逐层剥离叶子节点
        while (n > 2) { // 只剩下 <= 2 个节点时停止
            int size = queue.size();
            n -= size; // 剥离当前层叶子节点
            for (int i = 0; i < size; i++) {
                int leaf = queue.poll();
                for (int neighbor : graph.get(leaf)) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1) queue.offer(neighbor);
                }
            }
        }

        // 4. 剩下的节点就是 MHTs 的根
        while (!queue.isEmpty()) ans.add(queue.poll());
        return ans;
    }
}
